package Porject5Trees;

import java.util.ArrayList;

public class IOClass {

	/*
	 * This Creates a BST from a ArrayList
	 */
	public TreeNode Build(ArrayList<Integer> Numbers)
	{
		TreeNode BST = null;
		for (int i = 0; i < Numbers.size(); i++)
		{
			BST = AddNode(BST, Numbers.get(i));			
		}
		return BST;
	}
	
	/*
	 * This adds a Node to a BST
	 */
	private TreeNode AddNode(TreeNode BST, int NewNode)
	{
		if (BST != null)
		{
			if (NewNode > BST.Data)
			{
				BST.Right = AddNode(BST.Right, NewNode); 	
			}
			else
			{
				BST.Left = AddNode(BST.Left, NewNode); 					
			}
			return BST;
		}
		else
		{
			return new TreeNode(NewNode);
		}
	}
	
	/*
	 * This calls InOrder and adds Descriptive Text
	 */
	public void CallInOrder(TreeNode T1)
	{
		InOrder(T1);
		System.out.println("");
	}
	
	/*
	 * This Prints a BST inOrder
	 */
	public void InOrder(TreeNode BST)
	{
		if(BST != null)
		{
			InOrder(BST.Left);
			System.out.print(BST.Data + " ");
			InOrder(BST.Right);
		}
	}

	/*
	 * This calls PostOrder and adds Descriptive Text
	 */
	public void CallPostOrder(TreeNode T1)
	{
		PostOrder(T1);
		System.out.println("");
	}
	
	/*
	 * This prints a BST in PostOrder
	 */
	public void PostOrder(TreeNode BST)
	{

		if(BST != null)
		{
			PostOrder(BST.Left);		
			PostOrder(BST.Right);
			System.out.print(BST.Data + " ");
		}
	}
	
	/*
	 * This Calls Count and adds Descriptive Text
	 */
	public void CallCount(TreeNode T1)
	{
		System.out.println("The Tree has " + Count(T1) + " Leaf Nodes");
	}
	
	/*
	 * This Counts the Number of Leaf Nodes in a BST
	 */
	public int Count(TreeNode BST)
	{
		if (BST != null)
		{
			if (BST.Left == null && BST.Right == null)
			{
				return 1;
			}
			else
			{
				return Count(BST.Left) + Count(BST.Right);					
			}
		}
		else
		{
			return 0;
		}
	}
	
	/*
	 * This Counts the Number of Nodes in a BST
	 */
	public int CountNodes(TreeNode BST)
	{
		if (BST != null)
		{
			return 1 + Count(BST.Left) + Count(BST.Right);	
		}
		else
		{
			return 0;
		}
	}

	/*
	 *  This Swaps the Left and Right nodes of a Tree Recursively
	 */
	public TreeNode Swap(TreeNode BST)
	{
		if (BST != null)
		{
			TreeNode NewNode = new TreeNode(BST.Data);
			NewNode.Left = Swap(BST.Right);
			NewNode.Right = Swap(BST.Left);
			return NewNode;			
		}
		return null;
	}
	
	/*
	 * This Calls the Compare Functions and adds some decriptive text
	 */
	public void CallCompare(TreeNode T1, TreeNode T2)
	{
		if (Compare(T1, T2))
		{
			System.out.println("The Trees are Identical");
		}
		else
		{
			System.out.println("The Trees are NOT Identical");	
		}
		
	}
	
	/*
	 * This compares to BST to see if they are Identical
	 */
	public boolean Compare(TreeNode BST1, TreeNode BST2)
	{
		if (BST1 != null && BST2 != null)
		{
			if(BST1.Data != BST2.Data )
			{
				return false;
			}
			else
			{
				return (Compare(BST1.Left, BST2.Left) && Compare(BST1.Right, BST2.Right));
			}
		}
		else
		{
			if (BST1 == null && BST2 == null)
			{
				return true;
			}
			else
			{
				return false;
			}
		}


	}
	
	/*
	 * This Deletes a Node from a BST
	 */
	public TreeNode DeleteNode(TreeNode BST, int NodeValue)
	{
		if (BST != null)
		{
			if (BST.Data == NodeValue)
			{
				//Delete Node and adjust child nodes
				//No Child Nodes
				if (BST.Left == null && BST.Right == null)
				{
					return null;
				}
				else
				{
					if (BST.Left == null || BST.Right == null)
					{
						// ONE Child Node
						if (BST.Left == null)
						{
							return BST.Right;
						}
						else
						{
							return BST.Left;
						}
					}
					else
					{
						// TWO CHILD NODES
						TreeNode NewBST = new TreeNode(GetSmallestValue(BST.Right));
						NewBST.Left = BST.Left;
						NewBST.Right = DeleteNode(BST.Right, NewBST.Data);
						return NewBST;					
					}
				}
				
			}
			else
			{
				if(NodeValue > BST.Data)
				{
					BST.Right = DeleteNode(BST.Right, NodeValue);		
				}
				else
				{
					BST.Left = DeleteNode(BST.Left, NodeValue);				
				}
			}
		}
		return BST;
	}
	
	/*
	 * This returns the smallest value of a BST
	 */
	public int GetSmallestValue(TreeNode BST)
	{
		if (BST.Left == null)
		{
			return BST.Data;	
		}
		else
		{
			return GetSmallestValue(BST.Left);
		}
	}
	
	/*
	 * This returns the Specific node of a BST InORder
	 */
	public int GetInOrderNode(TreeNode BST, int Index)
	{
		ArrayList<Integer> InOrderArray = new ArrayList<Integer>();
		InOrderArray = BuildInOrderArray(BST, InOrderArray);		
		try
		{
			return InOrderArray.get(Index - 1);		
		}
		catch (Exception Ex)
		{
			System.out.println("Index does not exsist");
			return 0;
		}
	}
	
	/*
	 * This builts an InOrder Array from a BST
	 */
	public ArrayList<Integer> BuildInOrderArray(TreeNode BST, ArrayList<Integer> MyList)
	{
		if (BST != null)
		{
			MyList = BuildInOrderArray(BST.Left, MyList);
			MyList.add(BST.Data);
			MyList = BuildInOrderArray(BST.Right, MyList);		
		}
		return MyList;
	}
}
